package com.example.sortingalgorithm;

// 希尔排序
public class ShellSort {

    /**
     * 希尔排序（又称“缩小增量排序”）
     * 希尔排序是插入排序算法的一种优化方案，它基于插入排序算法的以下两个特点来给出改进方法：
     *   1.插入排序在待排序序列长度n比较小的时候，效率比较高
     *   2.插入排序在n值很大时，若待排序序列“基本有序”，那么效率依然比较高
     * 希尔排序的基本思路：
     *   先将整个待排序的序列分割成若干子序列，对每个子序列分别进行直接插入排序，待整个序列中的元素“基本有序”时，再对全体元素进行一次直接插入排序。
     * 比如：
     *   待排序序列：[5, 3, 4, 2, 1, 0]
     *   首先选择一个增量序列，这里选择希尔增量序列[n/2, (n/2)/2, ..., 1]，即[6/2=3, 6/2/2约等于1]
     *   首先使用增量gap=3对待排序序列进行分割，可以将待排序序列分割成3个子序列:
     *   [5, 2]，[3, 1]，[4, 0]
     *   接着分别对这3个子序列进行插入排序，排序完之后，整个序列变成这个样子：
     *   [2, 1, 0, 5, 3, 4]
     *   由于上面的增量序列中只有两个增量，而且最后一个增量gap是1，意味着把所有元素看作是一个序列，也就是[2, 1, 0, 5, 3, 4]，
     *   接下来对这个序列进行插入排序：
     *   [(2), 1, 0, 5, 3, 4] —— 这里是将2看作是有序序列
     *   [(1, 2), 0, 5, 3, 4] —— 这里将1从无序序列中抽出然后插入到有序序列中
     *   [(0, 1, 2), 5, 3, 4] —— 这里将0从无序序列中抽出然后插入到有序序列中
     *   [(0, 1, 2, 5), 3, 4] —— 这里将5从无序序列中抽出然后插入到有序序列中
     *   [(0, 1, 2, 3, 5), 4] —— 这里将3从无序序列中抽出然后插入到有序序列中
     *   [(0, 1, 2, 3, 4, 5)] —— 这里将4从无序序列中抽出然后插入到有序序列中，至此所有排序结束！
     * @param array
     * @param <T>
     */
    public static <T extends Comparable> void sort(T[] array){
        // gap存放增量
        for(int gap = array.length/2; gap >= 1; gap = gap/2){
            // 共gap组子序列，开始针对每一组子序列使用插入排序
            for(int group = 1; group <= gap; group++){
                // 0 + gap = 第一组子序列中第二个元素的下标；因此(group-1 +gap)表示当前这组子序列中第二个元素的下标
                // currentIndex指向当前要从子序列中抽出，然后插入到有序序列的元素的下标
                // currentElement用来临时存放从子序列中抽出的元素
                T currentElement;
                for(int currentIndex = (group-1 +gap); currentIndex < array.length; currentIndex+=gap){
                    // 将待进行插入排序的元素从子序列中抽出
                    currentElement = array[currentIndex];
                    // 开始对currentElement进行插入排序
                    // cursor指向有序序列中需要和当前元素进行比较的元素
                    // group-1表示当前子序列中的首元素的下标
                    for(int cursor = currentIndex - gap; cursor >= group-1; cursor -= gap){
                        if(currentElement.compareTo(array[cursor]) < 0){
                            // 当前元素比cursor指向的元素要小，那么需要将cursor指向的元素往后挪
                            array[cursor + gap] = array[cursor];
                            // 如果cursor指向的就是子序列中的首元素，那么currentElement的插入位置也就确定了
                            if(cursor == group-1){
                                array[cursor] = currentElement;
                                break;
                            }
                        }else {
                            array[cursor + gap] = currentElement;
                            break;
                        }
                    }
                }
            }

        }
    }

}
